package com.aqie.medium.dynamicProgram;

import java.util.*;

/**
 * 139 单词拆分 todo
 * s 是否可以被空格拆分为一个或多个在字典中出现的单词，字典词可重用
 */
public class WordBreak {
    /**
     * 1. 每一个前缀都在字典中，此时回溯树的复杂度会达O(n^n)
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, new HashSet(wordDict), 0);
    }
    private boolean wordBreak(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && wordBreak(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 2,记忆化回溯 O(n^2)
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        return wordBreak(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
    }


    private boolean wordBreak(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && wordBreak(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }


    /**
     * 3.DFS O(n^2)
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak3(String s, List<String> wordDict) {
        Set<String> wordDictSet=new HashSet(wordDict);
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[s.length()];
        queue.add(0);
        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (visited[start] == 0) {
                for (int end = start + 1; end <= s.length(); end++) {
                    if (wordDictSet.contains(s.substring(start, end))) {
                        queue.add(end);
                        if (end == s.length()) {
                            return true;
                        }
                    }
                }
                visited[start] = 1;
            }
        }
        return false;
    }

    /**
     * 4. DP
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak4(String s, List<String> wordDict) {
        Set<String> wordDictSet=new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }


    /**
     * 5. BFS剪枝方法，利用java内置函数，竟然出奇的快
    */
    String str;
    Set<Integer> cache;
    List<String> list;
    public boolean wordBreak5(String s, List<String> wordDict) {
        str=s;
        cache=new HashSet<Integer>();
        list=wordDict;
        return wordBreak(0);
    }
    private boolean wordBreak(int d){
        if(d == str.length()) return true;
        if(cache.contains(d)) return false;//无需再次重复计算，剪枝
        for(String word : list){
            if(str.startsWith(word, d)){
                if(wordBreak(d+word.length())) return true;
                cache.add(d+word.length());//已经为false的
            }
        }
        return false;
    }



    public static void main(String[] args) {
        String s = "applepenapple";
        String[] wordDict = {"apple", "pen"};
    }
}
